package com.cy.zcy;

/**
 * @Author: chenyun
 * @Date: 2021/09/23/15:10
 * @Description:
 */

//

/**
 * 题目：打印两个有序链表的公共部分  给定两个有序链表的头指针head1和head2，打印两个链表的公共部分
 * 要求：如果两个链表的长度之和为N，时间复杂度要求为O(N),额外空间复杂度要求为O(1)
 */
public class LinkDemo1 {
    //思路：因为是有序链表，所以谁小谁先移动，如果一样的则输出然后公共移动
    public static void commonPart(ListNode head1,ListNode head2){
        while (head1 != null && head2 != null){
            if(head1.val == head2.val){
                System.out.println(head1.val);
                head1 = head1.next;
                head2 = head2.next;
            }else if(head1.val > head2.val){
                head2 = head2.next;
            }else if(head2.val > head1.val){
                head1 = head1.next;
            }
        }

    }
    public static void main(String[] args) {
        ListNode A1 = new ListNode(2);
        ListNode A2 = new ListNode(5);
        ListNode A3 = new ListNode(8);
        ListNode B1 = new ListNode(5);
        ListNode B2 = new ListNode(9);
        A1.next = A2;
        A2.next = A3;
        A3.next = null;
        B1.next = B2;
        B2.next = null;
        commonPart(A1,B1);

    }
}
